POI2013 Tales of seafaring

POI
最短路

POI2013 Tales of seafaring

题目大意：

一个n个点，m条边的无向图，每一条边的边权都为1。有k个询问，每次询问给出(s,t,d)，要求回答是否存在一条从s到t的路径，长度为d。(路径可以不必是简单路(可以自交))

$PS.$ 感觉不是很难，有点像想法题。

题解：

仔细想想最后给的条件，不必是简单路意味着可以在两点之间来回走，从而有这么一个结论：若(s,t,d)可行，那么(s,t,d+2)也可行。(s不是孤立的点)

从而，思路就很简单了：找到s到t的最短奇路和最短偶路，根据询问d的奇偶性来与其中一个比较，若d比较大，说明我们可以利用来回走使其满足，否则不可行。

由于内存限制不能跑每一个点然后存下来，我们把询问离线处理，把起点相同的一起处理即可。

另外，此题还有一个小bug：若s是一个孤立的点，就不能够利用来回走来增加长度了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<queue>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=5005,Q=1000005;
int head[N],tot_edge;
struct Edge{
	int to,nxt;
}edge[N<<1];
void add_edge(int a,int b){
	edge[tot_edge]=(Edge){b,head[a]};
	head[a]=tot_edge++;
}
int n,m,k,sum[N];
struct Query{
	int s,t,d,id;
	bool operator <(const Query&tmp)const{
		return s<tmp.s;
	}
}q[Q];
bool ans[Q];
int dis[2][N];
struct node{
	bool tag;int p;
};
queue<node>que;
void BFS(int s){
	while(!que.empty())que.pop();
	memset(dis,-1,sizeof(dis));
	dis[0][s]=0,que.push((node){0,s});
	while(!que.empty()){
		node cur=que.front();que.pop();
		int p=cur.p;bool tag=cur.tag;
		for(int i=head[p];~i;i=edge[i].nxt){
			int to=edge[i].to;
			if(dis[tag^1][to]==-1)
				dis[tag^1][to]=dis[tag][p]+1,que.push((node){tag^1,to});
		}
	}
}
int main(){
	memset(head,-1,sizeof(head));
	Rd(n),Rd(m),Rd(k);
	for(int i=1,a,b;i<=m;i++){
		Rd(a),Rd(b);
		add_edge(a,b);
		add_edge(b,a);
		sum[a]++,sum[b]++;
	}
	for(int i=1;i<=k;i++){
		Rd(q[i].s),Rd(q[i].t),Rd(q[i].d),q[i].id=i;
	}
	sort(q+1,q+1+k);
	int cnt=0,ns;
	while(cnt<k){
		ns=q[cnt+1].s;
		BFS(ns);
		while(cnt<k&&q[cnt+1].s==ns){
			int id=q[cnt+1].id,t=q[cnt+1].t,d=q[cnt+1].d;
			bool tag=d%2;
			if(~dis[tag][t]&&(dis[tag][t]==d||dis[tag][t]<d&&sum[t]))ans[id]=true;
			else ans[id]=false;
			cnt++;
		}
	}
	for(int i=1;i<=k;i++){
		if(ans[i])printf("TAK\n");
		else printf("NIE\n");
	}
	return 0;
}
分享到 评论